package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=295&tqId=23286&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>BM11 链表相加(二)</a>
 *
 * @author c2b
 * @since 2024/3/14 11:07
 */
public class BM11AddInList {
    public static class Solution {
        public ListNode addInList(ListNode head1, ListNode head2) {
            if (head1 == null) {
                return head2;
            }
            if (head2 == null) {
                return head1;
            }
            head1 = reserve(head1);
            head2 = reserve(head2);
            ListNode dummy = new ListNode(-1);
            ListNode currNode = dummy;
            int carry = 0;
            while (head1 != null || head2 != null || carry != 0) {
                int sum = carry;
                if (head1 != null) {
                    sum += head1.val;
                    head1 = head1.next;
                }
                if (head2 != null) {
                    sum += head2.val;
                    head2 = head2.next;
                }
                carry = sum / 10;
                currNode.next = new ListNode(sum % 10);
                currNode = currNode.next;
            }
            return reserve(dummy.next);
        }

        private ListNode reserve(ListNode listNode) {
            if (listNode == null || listNode.next == null) {
                return listNode;
            }
            ListNode prevNode = null;
            ListNode currNode = listNode;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }
}
